package code;

//题目链接：https://leetcode.cn/problems/ones-and-zeroes/description/
//时间复杂度: O(L*M*N+T)，t为字符串元素的长度
public class FindMaxForm {
	public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j][k]: 从前i个元素中选，0不超过m个,1不超过n个，的最大子集长度
        int len=strs.length;
        int[][][] dp=new int[len+1][m+1][n+1];
        for(int i=1;i<=len;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    //统计strs[i-1]中0和1的个数
                    int a=0,b=0;
                    for(char c:strs[i-1].toCharArray()){
                        if(c=='0') a++;
                        else b++;
                    }
                    //不选i位置
                    dp[i][j][k]=dp[i-1][j][k];
                    //选i位置
                    if(j-a>=0&&k-b>=0){
                        dp[i][j][k]=Math.max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }
}
